package william.dp;

/**
 * @author ZhangShenao
 * @date 2024/1/8
 * @description <a href="https://leetcode.cn/problems/climbing-stairs/">...</a>
 */
public class Leetcode70_爬楼梯_动态规划 {

    /**
     * 采用动态规划算法
     * n阶楼梯的爬法=爬到n-1阶,最后爬1阶 + 爬到n-2阶,最后爬2阶
     * 初始解空间为: f(0)=1 f(1)=1
     * 状态转移公式: f(n)=f(n-1)+f(n-2)
     * <p>
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     */
    public int climbStairs(int n) {
        //边界条件校验
        if (n == 0 || n == 1) {
            return 1;
        }

        //定义初始解空间
        int lastLast = 1;
        int last = 1;
        int result = 0;

        //状态转移
        for (int i = 2; i <= n; i++) {
            result = lastLast + last;
            lastLast = last;
            last = result;
        }

        //返回结果
        return result;
    }

}
